package demo;
import java.util.Deque;
import java.util.LinkedList;
public class PostOrder {
    //构建二叉树
    public static TreeNode buildTree(){
        TreeNode n1=new TreeNode(1);
        TreeNode n2=new TreeNode(2);
        TreeNode n3=new TreeNode(3);
        TreeNode n4=new TreeNode(4);
        TreeNode n5=new TreeNode(5);
        TreeNode n6=new TreeNode(6);
        TreeNode n7=new TreeNode(7);

        n1.left=n2; n1.right=n3;
        n2.left=n4; n2.right=n5;
        n3.left=n6; n3.right=n7;

        return n1;

    }
    //非递归后序遍历
    //需要借助栈
    public static  void postOrder(TreeNode root){

        TreeNode cur=root;
        Deque<TreeNode> stack=new LinkedList<>();
        TreeNode last=null;
        while(cur!=null||!stack.isEmpty()){
            //先把左左边的结点依次放入栈中
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            //全部放入栈中以后查看栈顶元素是否有有右孩子（已经是最左边不可能有左孩子）
            TreeNode top=stack.peek();

            if(top.right==null){
                //如果没有右孩子直接出栈
                top=stack.pop();
                //打印结点元素
                System.out.println(top.val);
                //此处特别注意记得标记每一次已经出栈的元素
                last=top;
            }else if(top.right==last){
                //如果有右孩子但右孩子已经是标记过出栈的结点，则
                //相当于没有右孩子，也可以直接出栈
                top=stack.pop();
                System.out.println(top.val);
                //特别注意标记已经出栈元素
                last=top;
            }
           else {
               //如果有右孩子且右孩子未处理直接继续往右走
                cur=top.right;
            }
        }

    }
    public static void main(String[] args) {
        TreeNode root=buildTree();
        postOrder(root);

    }
}
